package Elementary_algorithm.Other;

import org.junit.Test;

/*
位1的个数
给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

示例 1：
输入：n = 11
输出：3
解释：输入的二进制串 1011中，共有 3 个设置位。
示例 2：
输入：n = 128
输出：1
解释：输入的二进制串 10000000中，共有 1 个设置位。
示例 3：
输入：n = 2147483645
输出：30
解释：输入的二进制串 1111111111111111111111111111101 中，共有 30 个设置位。

提示：
1 <= n <= 231 - 1
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn1m0i/
 */
public class _01位1的个数 {

    @Test
    public void test() {
        System.out.println(hammingWeight(2147483645));
    }

    //O(n)
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0){
            if (n % 2 == 1){
                count++;
            }
            n = n / 2;
        }
        return count;
    }

    //官解：方法二：位运算优化
    //观察这个运算：n & (n−1)，其运算结果恰为把n的二进制位中的最低位的1变为0之后的结果。
    //这样我们可以利用这个位运算的性质加速我们的检查过程，在实际代码中，我们不断让当前的n与n−1做与运算，直到n变为0即可。
    //因为每次运算会使得n的最低位的1被翻转，因此运算次数就等于n的二进制位中1的个数。
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/number-of-1-bits/solutions/672082/wei-1de-ge-shu-by-leetcode-solution-jnwf/
     */
    public class Solution {
        public int hammingWeight(int n) {
            int ret = 0;
            while (n != 0) {
                n &= n - 1;
                ret++;
            }
            return ret;
        }
    }


}
